// 枚举凸包 同向双指针:中间节点右移->最右节点的最佳答案更要向右移(若可以右移)
struct Vertex{
    int x, y;
    Vertex sub(const Vertex& v) const {
        return {x-v.x, y-v.y};
    }

    int cross(const Vertex& v) const { //两点的叉积:以这两条向量为边形成的平行四边形的面积
        return x*v.y-y*v.x;
    }
};

class Solution {
    vector<Vertex> convexHull(vector<Vertex> &points) //创建巡回凸包
    {
        ranges::sort(points, {}, [](auto &p) {return pair(p.x, p.y);}); //x升序 y升序
        vector<Vertex> q;

        //构建下凸包（从左到右）
        for(auto &p:points) {
            //若叉积<=0->当前点是凹陷点
            while(q.size()>1&&q[q.size()-1].sub(q[q.size()-2]).cross(p.sub(q[q.size()-1]))<=0) q.pop_back(); //维护凸包凸性
            q.push_back(p);
        }

        //计算上凸包（从右到左）
        int DownSize=q.size();
        //下凸包的最有一个点，是上凸包的右边的第一个点，从n-2开始遍历
        for(int i=points.size()-2; i>=0; i--)
        {
            auto &p=points[i];
            while(q.size()>DownSize&&q[q.size()-1].sub(q[q.size()-2]).cross(p.sub(q[q.size()-1]))<=0) q.pop_back();
            q.push_back(p);
        }
        q.pop_back(); //首尾是同一个最左点points[0]
        return q;
    }

    int area(vector<Vertex> &vertexs, int i, int j, int k)  //计算最大面积
    {return vertexs[j].sub(vertexs[i]).cross(vertexs[k].sub(vertexs[i]));}

public:
    double largestTriangleArea(vector<vector<int>>& points) {
        vector<Vertex> temp(points.size());
        for(int i=0; i<points.size(); i++) temp[i]={points[i][0], points[i][1]};

        vector<Vertex> vertexs=convexHull(temp);

        int n=vertexs.size();
        int ans=0;
        for(int i=0; i<n; i++)
        {
            //同向双指针
            int k=i+2;
            for(int j=i+1; j<n-1; j++)
            {
                while(k+1<n&&area(vertexs, i, j, k)<area(vertexs, i, j, k+1)) k++; //找到k的最大点
                ans=max(ans, area(vertexs, i, j, k));
            }
        }
        return ans/2.0;
    }
};